package mess;

import java.util.*;

public class LeeCode_15_Failed {
    public static void main(String[] args) {
        int[] nums = new int[]{-1,0,1,2,-1,-4,-2,-3,3,0,4};
        System.out.println(threeSum(nums));
    }
    private static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        //1.排序
        Arrays.sort(nums);
        //2.找出大于等于0起始索引
        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= 0){
                max = i;
                break;
            }
        }
        System.out.println(Arrays.toString(nums));
        //3.分两段匹配
        for (int i = 0; i <= max; i++) {
            if (i > 0 && nums[i] == nums[i - 1])
                continue;
            int first = nums[i];
            int add = 0;
            int second = 0;
            for (int j = i + 1; j <= nums.length - 1; j++) {
                if (j - 1 > i && nums[j] == nums[j - 1])
                    continue;
                second = nums[j];
                add = first + second;
                for (int k = j + 1; k < nums.length; k++) {
                    if (k - 1 > j && nums[k] == nums[k - 1])
                        continue;
                    if (add == 0 && k > j + 1)
                        continue;
                    if (nums[k] == -add){
                        List<Integer> list = new ArrayList<>();
                        list.add(first);
                        list.add(second);
                        list.add(nums[k]);
                        result.add(list);
                    }
                }
            }
        }
        return result;
    }
}
